import java.util.Arrays;

/**
 * 881. 救生艇
 * https://leetcode-cn.com/problems/boats-to-save-people/
 */
public class Solutions_881 {
    public static void main(String[] args) {
        int[] people = {1, 2};
        int limit = 3;  // output: 1

//        int[] people = {3, 2, 2, 1};
//        int limit = 3;  // output: 3

//        int[] people = {3, 5, 3, 4};
//        int limit = 5;  // output: 4

        int result = numRescueBoats(people, limit);
        System.out.println(result);
    }

    /**
     * 解题思路：
     * 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
     * 返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
     * 最重的和最轻的一块上船，即排序后，最左侧和最右侧的元素
     */
    public static int numRescueBoats(int[] people, int limit) {
        // 将 people 升序排列
        int res = 0;
        Arrays.sort(people);
        int left = 0, right = people.length - 1;
        while (left <= right) {
            // 贪心策略：每次，最重的一定要先上船
            int remind = limit - people[right];
            right --;
            // 船数量加 1
            res ++;
            if (remind >= people[left]) {
                // 坐上最重的后，剩余的重量还可以坐下最轻的，那么最轻的也上船
                left ++;
            }
        }
        return res;
    }
}
